#include <algorithm>
#include <cmath>
#include <iostream>
#include "BTreeNode.h"

using namespace std;

BTLeafNode::BTLeafNode()
{
  nextNode = EMPTY_VALUE;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  if (pid < 0)
    return RC_INVALID_PID;

  // Read page from pagefile into buffer.
  char page[PageFile::PAGE_SIZE];
  RC ret = pf.read(pid, page);
  if (ret != 0)
    return ret;

  BTNodeByteBuffer nbb(page);

  // Read next node pointer.
  nbb.readInt(nextNode);

  // Read entries from buffer.
  entries.clear();
  for (int i = 0; i < MAX_ENTRIES; i++) {
    int key;
    RecordId rid;

    // Read RecordId.
    nbb.readInt(rid.pid);
    nbb.readInt(rid.sid);

    // Read key.
    nbb.readInt(key);

    if (key == EMPTY_VALUE && rid.pid == EMPTY_VALUE && rid.sid == EMPTY_VALUE)
      break;

    insert(key, rid);
  }

  return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  if (pid < 0)
    return RC_INVALID_PID;

  BTNodeByteBuffer nbb;

  // Write next node pointer.
  nbb.appendInt(nextNode);

  // Write entries to buffer.
  for (int i = 0; i < getKeyCount(); i++) {
    int key;
    RecordId rid;
    readEntry(i, key, rid);

    // Write RecordId.
    nbb.appendInt(rid.pid);
    nbb.appendInt(rid.sid);

    // Write key.
    nbb.appendInt(key);
  }

  // Write buffer to page in pagefile.
  return pf.write(pid, nbb.rawBuffer());
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount() const
{
  return entries.size();
}

/*
 * Insert a (key, rid) pair to the node (does not check if the node is full).
 * This is for internal use only.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 */
void BTLeafNode::unchecked_insert(int key, const RecordId& rid)
{
  entries.push_back(BTLeafNodeEntry(key, rid));
  sort(entries.begin(), entries.end());
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  if (getKeyCount() >= MAX_ENTRIES)
    return RC_NODE_FULL;
  if (rid.pid < 0 || rid.sid < 0)
    return RC_INVALID_RID;
  unchecked_insert(key, rid);
  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey)
{
  if (rid.pid < 0 || rid.sid < 0)
    return RC_INVALID_RID;

  if (sibling.getKeyCount() != 0)
    return RC_NODE_NOT_EMPTY;

  // We use unchecked_insert() since we allow any temporary overflow.
  unchecked_insert(key, rid);

  // Calculate the split point. This is the index of the first entry to be
  // moved to the sibling node.
  int splitPoint = (int)ceil((double)getKeyCount() / (double)2);
  siblingKey = entries[splitPoint].key();

  // Step 1 of split: Copy entries to the sibling node.
  for (int i = splitPoint; i < getKeyCount(); i++) {
    int key;
    RecordId rid;
    readEntry(i, key, rid);
    sibling.insert(key, rid);
  }

  // Step 2 of split: Delete the copied entries from the current node.
  entries.erase(entries.begin() + splitPoint, entries.end());

  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid) const
{
  for (int i = 0; i < getKeyCount(); i++) {
    if (entries[i].key() >= searchKey) {
      eid = i;
      return 0;
    }
  }
  return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid) const
{
  if (eid < 0 || eid >= getKeyCount())
    return RC_INVALID_CURSOR;
  key = entries[eid].key();
  rid = entries[eid].rid();
  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node
 */
PageId BTLeafNode::getNextNodePtr() const
{
  return nextNode;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  nextNode = pid;
  return 0;
}

/*
 * Print the contents of the node (for debugging purposes).
 * @param name[IN] give this node an informative name to be printed
 */
void BTLeafNode::print(const std::string& name) const
{
  for (int i = 0; i < getKeyCount(); i++) {
    int key;
    RecordId rid;
    readEntry(i, key, rid);
    cerr << "Leaf Node '" << name << "' Entry eid = " << i << ": key = " << key << ", rid.pid = " << rid.pid << ", rid.sid = " << rid.sid << endl;
  }
}

BTNonLeafNode::BTNonLeafNode()
{
  pidFirst = EMPTY_VALUE;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  if (pid < 0)
    return RC_INVALID_PID;

  // Read page from pagefile into buffer.
  char page[PageFile::PAGE_SIZE];
  RC ret = pf.read(pid, page);
  if (ret != 0)
    return ret;

  BTNodeByteBuffer nbb(page);

  // Read first PageId.
  nbb.readInt(pidFirst);

  // Read entries from buffer.
  entries.clear();
  for (int i = 0; i < MAX_ENTRIES; i++) {
    int key;
    PageId pid;

    nbb.readInt(key);
    nbb.readInt(pid);

    if (key == EMPTY_VALUE && pid == EMPTY_VALUE)
      break;

    insert(key, pid);
  }

  return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  if (pid < 0)
    return RC_INVALID_PID;

  BTNodeByteBuffer nbb;

  // Write first PageId.
  nbb.appendInt(pidFirst);

  // Write entries to buffer.
  for (int i = 0; i < getKeyCount(); i++) {
    nbb.appendInt(entries[i].key());
    nbb.appendInt(entries[i].pid());
  }

  // Write buffer to page in pagefile.
  return pf.write(pid, nbb.rawBuffer());
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount() const
{
  return entries.size();
}

/*
 * Insert a (key, pid) pair to the node (does not check if the node is full).
 * This is for internal use only.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 */
void BTNonLeafNode::unchecked_insert(int key, PageId pid)
{
  entries.push_back(BTNonLeafNodeEntry(key, pid));
  sort(entries.begin(), entries.end());
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  if (getKeyCount() >= MAX_ENTRIES)
    return RC_NODE_FULL;
  if (pid < 0)
    return RC_INVALID_PID;
  unchecked_insert(key, pid);
  return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  if (pid < 0)
    return RC_INVALID_PID;

  if (sibling.getKeyCount() != 0)
    return RC_NODE_NOT_EMPTY;

  // We use unchecked_insert() since we allow any temporary overflow.
  unchecked_insert(key, pid);

  // Calculate the split point. This is the index of the entry to be extracted
  // as the mid key. Everything after the mid key will be moved to the sibling.
  int splitPoint = (int)floor((double)getKeyCount() / (double)2);
  midKey = entries[splitPoint].key();

  // Step 1 of split: Copy entries to the sibling node.
  sibling.initializeRoot(entries[splitPoint].pid(), entries[splitPoint + 1].key(), entries[splitPoint + 1].pid());
  for (int i = splitPoint + 2; i < getKeyCount(); i++)
    sibling.insert(entries[i].key(), entries[i].pid());

  // Step 2 of split: Delete the copied entries from the current node.
  entries.erase(entries.begin() + splitPoint, entries.end());

  return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid) const
{
  if (searchKey < entries[0].key()) {
    pid = pidFirst;
    return 0;
  }

  for (int i = 0; i < getKeyCount() - 1; i++) {
    if (searchKey >= entries[i].key() && searchKey < entries[i + 1].key()) {
      pid = entries[i].pid();
      return 0;
    }
  }

  if (searchKey >= entries[getKeyCount() - 1].key()) {
    pid = entries[getKeyCount() - 1].pid();
    return 0;
  }

  return RC_NO_SUCH_RECORD;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  if (pid1 < 0 || pid2 < 0)
    return RC_INVALID_PID;
  pidFirst = pid1;
  return insert(key, pid2);
}

/*
 * Print the contents of the node (for debugging purposes).
 * @param name[IN] give this node an informative name to be printed
 */
void BTNonLeafNode::print(const std::string& name) const
{
  cerr << "Non-Leaf Node '" << name << "': pid = " << pidFirst << " contains keys < " << entries[0].key() << endl;
  for (int i = 0; i < getKeyCount() - 1; i++)
    cerr << "Non-Leaf Node '" << name << "': pid = " << entries[i].pid() << " contains keys >= " << entries[i].key() << " but < " << entries[i + 1].key() << endl;
  cerr << "Non-Leaf Node '" << name << "': pid = " << entries[getKeyCount() - 1].pid() << " contains keys >= " << entries[getKeyCount() - 1].key() << endl;
}
